#include <iostream>
#include <malloc.h> 
#include <string>
using namespace std;

void printArray(string array[], int arrLen) {
    for (int i = 0; i < arrLen; ++i) {
        cout << array[i] << " ";
    }
    cout << endl;
}

void radixSort (string array[],int n){ 
	string *result = new string [n] (); //结果数组
	int  *coutArray =  new int [127](); //计数数组
	int Max = 1;//定义最大位 
	for(int i = 0;i <n;i++){//获取最大位 
		int Max_1 =array[i].length();
		if (Max < Max_1){
			Max = Max_1;
		}
	}
	for (int i = Max-1 ;i>=0;i--){ //进行最大位的循环 
		for (size_t j = 0; j< 127; ++j){
          	coutArray[j] = 0; //初始化
   		}
		for (int j = 0;j<n;j++) {
			int num = array[j].at(i);   //获取字符串尾字符的Ascll码
			coutArray[num] ++;  //在对应的地方加1
		}
		for (int j = 1; j<127;j++){ 
			coutArray [j] = coutArray[j] + coutArray[j-1];//求和
		} 
		for (int j = n-1;j>=0;j--){ //基数排序 
			int num = array[j].at(i);
			result[coutArray[num]-1] = array[j];
			coutArray[num] --; 
		}
		for(int i = 0;i<n;i++){
			array[i] = result[i];//复制
		}
	}
} 
int main (){
 	string array[] = {"abc","qwe","asd","zxc"};
 	int n =sizeof(array) / sizeof(array[0]);
    cout<<"输入的数组：";
 	printArray(array,n);
 	radixSort(array,n); 
 	cout<<"排序后数组：";
 	printArray(array,n);

}